package 二分.二分答案;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/6 10:53
 */
public class Note板子 {
    /*
     这些板子 有一些 非常 致命的问题,
     就是 二分查找 找不到 结果的情况,
     也就是 集合中, 没有 该要找的值, 这种情况, 就是两个 点 一个 是
     0, 一个 nums.length - 1, 这是 找不到 值得情况下 会返回 这两个 其中得一个,
     这是因为你得代码 决定的, 但是这种 还有一个问题,就是 ,可能 正确的 ans 也刚好是 0  or nums.length - 1
     所以 这种还要 在 返回的 时候, 做一些 特判 才行!
     */


    /*
      二分的 板子 :
      至于 写成 第一种 板子 ,还是 写成 第二种 板子 要根据 题目的条件 进行判断了
      牢记 这两种板子
      就两种情况:
      ① [l , mid] , [mid + 1, r]
      这种板子 对应的 就是 l = mid + 1, r = mid


      ②[l , mid - 1] , [mid , r]
      这种板子 对应的 就是 : r = mid - 1, l = mid
      但是 在 求 mid 的时候 需要 ＋ 1 (主要是为了 避免 死循环)
      mid = l + r + 1 >> 1;
     */


    /*
      注意 这类 题目的 一个 特点：
      题目 原本 是：
      条件 + 限制  ----->  答案

      按照 二分 答案的思路 :

      二分 答案  + 条件  -------> 限制 (是否 符合 给定的 限制)

      所以 考虑的 三个 点:
      1. 答案的 范围
      2. 是否存在 与答案 相关联的  **单调性**(或者说, 能把整个 数据 一分为二的 特性)
      3.  答案 + 条件  ---> 限制  (这个  函数 怎么 写)
      4. 数据量的 范围, 这个也是 一个 比较 重要点 (一般常规的 思虑 的 复杂度 ,明显 会超时!)
     */


        /*
    下面的 链接  : 灵神 还记录 相关 的类似的 题目!
    https://leetcode.cn/problems/house-robber-iv/solutions/2093952/er-fen-da-an-dp-by-endlesscheng-m558/
     最优解是 二分 答案 :

     最重要的 还是 ** 单调性  **

     这个 题 搞明之后 , 把上面的 链接上面的 题, 以及  **四边形不等式** 的那几个  **最化最值** 的问题
     给弄明白!
     顺便 再 看下 灵神的   ** 二分  和 回溯 ** 相关 模板的 讲解!

     */

    /*
        也是 一些 二分答案的 题目
        lc 275
        lc 611
        lc 1011
        lc 1482
     */

    public int binaryTemplate(int arr[],int target){
        int l = 0,r = arr.length - 1;
        while(l < r ){
            int mid = l + r + 1 >> 1;
            if(arr[mid] > target){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        return l;
    }

    public static void main(String[] args) {
//        int nums[] = {1,2,4,5,5,5,5,5,7,9};
//        int i = new Note板子().binaryTemplate(nums, 3);
//        System.out.println(i);
    }

}
